﻿

@article{BannaiIInenagaNakashimaTakedaTsuruta,
  title={The ``runs'' theorem},
  author={Bannai, H. and I, T. and Inenaga, S. and Nakashima, Y. and Takeda, M. and Tsuruta, K.},
  journal={arXiv preprint arXiv:1406.0263v4},
  year={2014}
}
@incollection{BenderColeDemaineFarachColtonZito,
  title={{Two simplified algorithms for maintaining order in a list}},
  author={Bender, M. A. and Cole, R. and Demaine, E. D. and Farach-Colton, M. and Zito, J.},
  booktitle={Algorithms-ESA 2002},
  volume={2461},
  series={LNCS},
  pages={152--164},
  year={2002},
  publisher={Springer},
  doi={10.1007/3-540-45749-6_17}
}
@article{BilleGortzSachVildhoj,
  title={{Time-space trade-offs for longest common extensions}},
  author={Bille, P. and G{\o}rtz, I. L. and Sach, B. and Vildh{\o}j, H. W.},
  journal={J. of Discrete Algorithms},
  volume={25},
  pages={42--50},
  year={2014},
  publisher={Elsevier},
  doi={10.1007/978-3-642-31265-6_24}
}
@article{BlandSmyth,
  title={Three overlapping squares: the general case characterized \& applications},
  author={Bland, W. and Smyth, W. F.},
  journal={Theoretical Computer Science},
  year={2015},
  volume={596},
  pages={23--40},
  publisher={Elsevier},
  doi={doi:10.1016/j.tcs.2015.06.037}
}
@inproceedings{BreslauerGrossiMignosi,
  title={Simple real-time constant-space string matching},
  author={Breslauer, D. and Grossi, R. and Mignosi, F.},
  booktitle={CPM 2011},
  pages={173--183},
  year={2011},
  publisher={Springer},
  doi={10.1007/978-3-642-21458-5_16}
}
@inproceedings{BurkhardtKarkkainen,
  title={{Fast lightweight suffix array construction and checking}},
  author={Burkhardt, S. and K{\"a}rkk{\"a}inen, J.},
  booktitle={CPM 2003},
  volume={2676},
  series={LNCS},
  pages={55--69},
  year={2003},
  publisher={Springer},
  doi={10.1007/3-540-44888-8_5}
}
@article{CesariVincent,
  title={Une caract{\'e}risation des mots p{\'e}riodiques},
  author={C{\'e}sari, Y. and Vincent, M.},
  journal={CR Acad. Sci. Paris},
  volume={286},
  number={A},
  pages={1175--1177},
  year={1978},
  doi={10.1016/0012-365X(79)90146-8}
}
@article{CrochemorePerrin,
  title={Two-way string-matching},
  author={Crochemore, M. and Perrin, D.},
  journal={Journal of the ACM (JACM)},
  volume={38},
  number={3},
  pages={650--674},
  year={1991},
  publisher={ACM},
  doi={10.1145/116825.116845}
}
@article{Duval,
  title={Factorizing words over an ordered alphabet},
  author={Duval, J.-P.},
  journal={Journal of Algorithms},
  volume={4},
  number={4},
  pages={363--381},
  year={1983},
  publisher={Elsevier},
  doi={10.1016/0196-6774(83)90017-2}
}
@article{DuvalEtAl,
  title={Linear-time computation of local periods},
  author={Duval, J.-P. and Kolpakov, R. and Kucherov, G. and Lecroq, T. and Lefebvre, A.},
  journal={Theoretical Computer Science},
  volume={326},
  number={1},
  pages={229--240},
  year={2004},
  publisher={Elsevier},
  doi={10.1016/j.tcs.2004.06.024}
}
@article{DuvalLecroqLefebvre,
  title={Linear computation of unbordered conjugate on unordered alphabet},
  author={Duval, J.--P. and Lecroq, T. and Lefebvre, A.},
  journal={Theoretical Computer Science},
  volume={522},
  pages={77--84},
  year={2014},
  publisher={Elsevier},
  doi={doi:10.1016/j.tcs.2013.12.008}
}
@article{FischerHolubILewenstein,
  title={Beyond the runs theorem},
  author={Fischer, J. and Holub, S. and I, T. and Lewenstein, M.},
  journal={arXiv preprint arXiv:1502.04644},
  year={2015}
}
@inproceedings{FranceschiniGrossi,
  title={A general technique for managing strings in comparison-driven data structures},
  author={Franceschini, G. and Grossi, R.},
  booktitle={ICALP 2004},
  series={LNCS},
  volume={3142},
  pages={606--617},
  year={2004},
  publisher={Springer},
  doi={10.1007/978-3-540-27836-8_52}
}
@article{GalilSeiferas,
  title={Time-space-optimal string matching},
  author={Galil, Z. and Seiferas, J.},
  journal={Journal of Computer and System Sciences},
  volume={26},
  number={3},
  pages={280--294},
  year={1983},
  publisher={Elsevier},
  doi={10.1016/0022-0000(83)90002-8}
}
@book{Gusfield,
  title={Algorithms on strings, trees and sequences: computer science and computational biology},
  author={Gusfield, D.},
  year={1997},
  publisher={Cambridge university press},
  doi={10.1017/CBO9780511574931}
}
@article{HarelTarjan,
  title={Fast algorithms for finding nearest common ancestors},
  author={Harel, D. and Tarjan, R. E.},
  journal={SIAM Journal on Computing},
  volume={13},
  number={2},
  pages={338--355},
  year={1984},
  publisher={SIAM},
  doi={10.1137/0213024}
}
@inproceedings{KolpakovKucherov,
  title={Finding maximal repetitions in a word in linear time},
  author={Kolpakov, R. and Kucherov, G.},
  booktitle={FOCS 1999},
  pages={596--604},
  year={1999},
  publisher={IEEE},
  doi={10.1109/SFFCS.1999.814634}
}
@inproceedings{KopelowitzLewenstein,
  title={{Dynamic weighted ancestors}},
  author={Kopelowitz, T. and Lewenstein, M.},
  booktitle={SODA 2007},
  pages={565--574},
  year={2007},
  publisher={SIAM},
  doi={10.1145/1283383.1283444}
}
@inproceedings{Kosolobov,
  author = {Kosolobov, D.},
  title = {{Lempel-Ziv factorization may be harder than computing all runs}},
  booktitle = {STACS 2015},
  volume = {30},
  series = {LIPIcs},
  pages = {582--593},
  year = {2015},
  publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  doi = {10.4230/LIPIcs.STACS.2015.582}
}
@inproceedings{Kosolobov2,
  author    = {Kosolobov, D.},
  title     = {Online detection of repetitions with backtracking},
  booktitle = {CPM 2015},
  pages     = {295--306},
  year      = {2015},
  publisher={Springer},
  doi       = {10.1007/978-3-319-19929-0_25}
}
@article{Kosolobov3,
  title={{Faster lightweight Lempel-Ziv parsing}},
  author={Kosolobov, D.},
  journal={arXiv preprint arXiv:1504.06712},
  year={2015}
}
@article{Kosolobov4,
  title={Computing Runs on a General Alphabet},
  author={Kosolobov, D.},
  journal={arXiv preprint arXiv:1507.01231},
  year={2015}
}
@article{Main,
  title={Detecting leftmost maximal periodicities},
  author={Main, M. G.},
  journal={Discrete Applied Mathematics},
  volume={25},
  number={1},
  pages={145--153},
  year={1989},
  publisher={Elsevier},
  doi={10.1016/0166-218X(89)90051-6}
}
@incollection{MainLorentz,
  title={Linear time recognition of squarefree strings},
  author={Main, M. G. and Lorentz, R. J.},
  booktitle={Combinatorial Algorithms on Words},
  pages={271--278},
  year={1985},
  publisher={Springer},
  doi={10.1007/978-3-642-82456-2_18}
}
@article{HongChen,
  title={Efficient on-line repetition detection},
  author={Hong, J.-J. and Chen, G.-H.},
  journal={Theoretical Computer Science},
  volume={407},
  number={1},
  pages={554--563},
  year={2008},
  publisher={Elsevier},
  doi={10.1016/j.tcs.2008.08.038}
}

@book{Lothaire,
  title={Combinatorics on words},
  author={Lothaire, M.},
  year={1997},
  publisher={Cambridge University Press},
  doi={10.1017/CBO9780511566097}
}

@incollection{ShurPetrova,
  title={On the tree of ternary square-free words},
  author={Shur, A. M. and Petrova, E. A.},
  booktitle={Proc. 10th Internat. Conf. on Words (WORDS 2015)},
  volume={9304},
  series={LNCS},
  pages={0--0},
  year={2015},
  publisher={Springer},
  doi={0}
}
@incollection{BenderColeDemaineFarachColtonZito,
  title={{Two simplified algorithms for maintaining order in a list}},
  author={Bender, M. A. and Cole, R. and Demaine, E. D. and Farach-Colton, M. and Zito, J.},
  booktitle={Algorithms-ESA 2002},
  volume={2461},
  series={LNCS},
  pages={152--164},
  year={2002},
  publisher={Springer},
  doi={10.1007/3-540-45749-6_17}
}
